def johnson_schedule(jobs):
    """
    Johnson算法实现双机流水作业调度
    :param jobs: 作业列表，每个作业需包含'id'(标识), 'a'(机器1时间), 'b'(机器2时间)
    :return: (调度顺序, 总完成时间)
    """
    # 将作业分为两组
    group1 = [job for job in jobs if job['a'] <= job['b']]  # a_i <= b_i
    group2 = [job for job in jobs if job['a'] > job['b']]  # a_i > b_i

    # 分别排序：group1按a升序，group2按b降序
    group1_sorted = sorted(group1, key=lambda x: x['a'])
    group2_sorted = sorted(group2, key=lambda x: -x['b'])

    # 合并调度顺序
    schedule = group1_sorted + group2_sorted

    # 计算总完成时间
    machine1_time = 0
    machine2_time = 0
    for job in schedule:
        machine1_time += job['a']
        machine2_start = max(machine1_time, machine2_time)
        machine2_time = machine2_start + job['b']

    return [job['id'] for job in schedule], machine2_time


# 示例测试
if __name__ == "__main__":
    # 测试用例1：文献中的经典案例
    jobs_case1 = [
        {'id': 'A', 'a': 3, 'b': 6},
        {'id': 'B', 'a': 5, 'b': 2},
        {'id': 'C', 'a': 1, 'b': 7},
        {'id': 'D', 'a': 6, 'b': 4},
        {'id': 'E', 'a': 7, 'b': 4}
    ]

    # 测试用例2：用户问题中的示例
    jobs_case2 = [
        {'id': 'E', 'a': 7, 'b': 4},
        {'id': 'F', 'a': 5, 'b': 3}
    ]

    for case in [jobs_case1, jobs_case2]:
        order, total_time = johnson_schedule(case)
        print(f"最优调度顺序：{order}")
        print(f"总完成时间：{total_time}\n")
